﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="CheapestInsertion.cs" company="Luis de la Torre">
//   Copyright Luis de la Torre, unless otherwise indicated
// </copyright>
// <summary>
//   The cheapest insertion.
// </summary>
// --------------------------------------------------------------------------------------------------------------------

namespace PVRP_SR
{
    using System;
    using System.Diagnostics;

    /// <summary>
    /// The cheapest insertion.
    /// </summary>
    internal class CheapestInsertion : ConstructionHeuristic
    {
        #region Public Methods and Operators

        /// <summary>
        /// The create solution.
        /// </summary>
        /// <param name="instance">
        /// The instance.
        /// </param>
        /// <returns>
        /// The <see cref="PvrpSrSolution"/>.
        /// </returns>
        public override PvrpSrSolution CreateSolution(TSPLIBParser instance)
        {
            PvrpSrSolution solution = new PvrpSrSolution(instance);
            solution.EmptySolution();
            this.RunCheapestInsertion(solution);
            return solution;
        }

        #endregion

        #region Methods

        /// <summary>
        /// Find the node with cheapest insertion that needs to be visited in the current day but is not yet scheduled
        /// </summary>
        /// <param name="solution">
        /// PVRP solution to modify
        /// </param>
        /// <param name="t">
        /// current day, to check for schedule 
        /// </param>
        /// <returns>
        /// The <see cref="InsertionPoint"/>.
        /// </returns>
        private InsertionPoint FindCheapestInsertionPoint(PvrpSrSolution solution, int t)
        {
            int cheapestInsertionNode = -1;
            int cheapestInsertionVehicle = -1;
            int cheapestInsertionPredecessor = -1;
            double cheapestInsertionCost = double.MaxValue;
            double cheapestInsertionDistance = double.MaxValue;

            // check for the cost of inserting customer i after node pred
            for (int i = 1; i < solution.Instance.NumNodesRegular; i++)
            {
                // only check nodes that are scheduled for day t and not routed
                if (!(solution.Instance.Demands[t][i] > 0))
                {
                    continue;
                }

                if (solution.IsRouted(t, i))
                {
                    continue;
                }

                for (int k = 0; k < solution.Instance.NumVehicles; k++)
                {
                    // loop through possible insertion points
                    // can't insert after the last node in the route
                    for (int predIdx = 0; predIdx < solution.Routes[t, k].Nodes.Count - 1; predIdx++)
                    {
                        int pred = solution.Routes[t, k].Nodes[predIdx];

                        // this is the cheapest point and route if it is the cheapest yet 
                        double currentInsertionCost = solution.InsertionCost(i, t, pred, k);
                        double currentInsertionDistance = solution.InsertionDistance(i, t, pred, k);
                        Debug.Assert(
                            currentInsertionCost >= currentInsertionDistance, 
                            "insertion cost must be larger than insertion distance");
                        if (!(currentInsertionCost < cheapestInsertionCost))
                        {
                            continue;
                        }

                        cheapestInsertionNode = i;
                        cheapestInsertionVehicle = k;
                        cheapestInsertionPredecessor = pred;
                        cheapestInsertionCost = currentInsertionCost;
                        cheapestInsertionDistance = currentInsertionDistance;
                    }
                }
            }

            return new InsertionPoint(
                cheapestInsertionNode, 
                cheapestInsertionVehicle, 
                cheapestInsertionPredecessor, 
                cheapestInsertionCost, 
                cheapestInsertionDistance);
        }

        /// <summary>
        /// The run cheapest insertion.
        /// </summary>
        /// <param name="solution">
        /// The solution.
        /// </param>
        /// <exception cref="ArgumentNullException">
        /// Throws null exception if the solution is null.
        /// </exception>
        private void RunCheapestInsertion(PvrpSrSolution solution)
        {
            if (solution == null)
            {
                throw new ArgumentNullException("solution");
            }

            Debug.Assert(solution.Instance.StartDepots.Length == 1, "only one depot allowed");

            for (int t = 0; t < solution.Instance.NumDays; t++)
            {
                while (!solution.IsDayRouteFeasible(t))
                {
#if DEBUG
                    solution.PrintSolution();
#endif

                    InsertionPoint insertion = this.FindCheapestInsertionPoint(solution, t);
                    solution.Insert(t, insertion);
                }
            }
        }

        #endregion
    }
}